'''
https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/description/
'''
import bisect
from typing import List
class Solution:

    # 分成k组，对每一组求最长不递增子序列
    def kIncreasing(self, arr: List[int], k: int) -> int:
        n = len(arr)

        def len_not_LIS(start):
            ends = []
            size = 0
            for i in range(start, n, k):
                find = bisect.bisect_right(ends, arr[i])
                if find == len(ends) or ends[find] == arr[i]:
                    ends.append(arr[i])
                else:
                    ends[find] = arr[i]
                size += 1
            return size - len(ends)
        ans = 0
        for i in range(k):
            ans += len_not_LIS(i)
        return ans

nums = [12,6,12,6,14,2,13,17,3,8,11,7,4,11,18,8,8,3]
k = 1
print(Solution().kIncreasing(nums, k))